//log : 

#include <stdio.h>

typedef struct Muble{
    int left;
    int right;
    int sum;
}Muble;

Muble findMaxSubarray(int arr[],int l,int r)
{
    printf("entry findMaxSubarray\n");
    //int tmpSum = -0x3f3f3f3f;
    int left = 0,right = 0;
    int leftSum = 0,rightSum = 0;
    leftSum = rightSum = -0x3f3f3f3f;
    int mid = (l+r)>>1;
    int i = 0,sum = 0;
    for(i = mid;i>=l;--i)
    {
        sum+=arr[i];
        if(sum>leftSum)
        {
            leftSum = sum;
            left = i;
        }
    }
    sum = 0;
    for(i = mid+1;i<=r;++i)
    {
        sum+=arr[i];
        if(sum>rightSum)
        {
            rightSum = sum;
            right = i;
        }
    }
    Muble muble = {left,right,leftSum+rightSum};
    printf("return muble\n");
    return muble;
}

Muble mergerSubarray(int arr[],int l,int r)
{
    printf("l = %d,r = %d entry mergerSubarray()\n",l,r);
    if(l == r)
    {
        Muble muble = {l,r,arr[l]};
        return muble;
    }
    int mid = (l+r)>>1;
    Muble muble1,muble2,muble3;
    muble1 = mergerSubarray(arr,l,mid);
    muble2 = mergerSubarray(arr,mid+1,r);
    muble3 = findMaxSubarray(arr,l,r);
    printf("comtest\n");
    if(muble1.sum>muble2.sum&&muble1.sum>muble3.sum)
        return muble1;
    else if(muble2.sum>muble1.sum&&muble2.sum>muble3.sum)
        return muble2;
    else 
        return muble3;

}

int main()
{
    int arr[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    int length = sizeof(arr)/sizeof(int);
    Muble muble = mergerSubarray(arr,0,length-1);
    printf("l = %d,r = %d,ans = %d",muble.left,muble.right,muble.sum);
    return 0;
}
